package com.practice.niuke.new_direct_basics.class15;

/**
 * 象棋中马的跳法
 * 【题目】
 * 请同学们自行搜索或者想象一个象棋的棋盘， 然后把整个棋盘放入第一象限， 棋盘的最左下
 * 角是(0,0)位置。 那么整个棋盘就是横坐标上9条线、 纵坐标上10条线的一个区域。 给你三个
 * 参数， x， y， k， 返回如果“马” 从(0,0)位置出发， 必须走k步， 最后落在(x,y)上的方法数
 * 有多少种？
 */
public class Code04_HorseJump {


    /**
     * （1）暴力递归法(TODO: 暴力递归主函数)
     * 从(0,0)位置出发, 要去往(a,b)位置，必须跳k步，返回方法数
     *
     * @param a    目的地位置的“纵坐标”
     * @param b    目的地位置的“横坐标”
     * @param step 必须要走step步
     * @return int
     */
    public static int ways(int a, int b, int step) {
        // 从(0,0)位置出发
        // 要去往(a,b)位置，必须跳step步，
        // 返回方法数
        return f(0, 0, step, a, b);
    }


    /**
     * （1）暴力递归法：
     * 马现在来到(i, j)位置，还有step步要跳，最后到达(a, b)这个目的地位置的方法数。
     *
     * @param i    马现在所在位置的“纵坐标”
     * @param j    马现在所在位置的“横坐标”
     * @param step 还有step步要跳
     * @param a    目的地位置的“纵坐标”，固定参数
     * @param b    目的地位置的“横坐标”，固定参数
     * @return int
     */
    public static int f(int i, int j, int step, int a, int b) {
        // 棋盘是10*9；
        // 行数范围0~9, 也就是纵坐标i的范围是0~9
        // 列数范围0~8，也就是横坐标j的范围是0~8
        if (i < 0 || i > 9 || j < 0 || j > 8) {
            // 越界
            return 0;
        }
        // 没有步数可以走了，如果当前就在(a, b)位置则返回1种方法数，如果当前不在(a, b)位置则范围0种方法数。
        if (step == 0) {
            return (i == a && j == b) ? 1 : 0;
        }
        return f(i - 1, j + 2, step - 1, a, b) +
                f(i - 2, j + 1, step - 1, a, b) +
                f(i - 2, j - 1, step - 1, a, b) +
                f(i - 1, j - 2, step - 1, a, b) +
                f(i + 1, j - 2, step - 1, a, b) +
                f(i + 2, j - 1, step - 1, a, b) +
                f(i + 2, j + 1, step - 1, a, b) +
                f(i + 1, j + 2, step - 1, a, b);
    }

    /**
     * "暴力递归"改为"动态规划"（TODO: 暴力递归改动态规划）
     *
     * @param a 目的地位置的“纵坐标”
     * @param b 目的地位置的“横坐标”
     * @param s 必须要走s步
     * @return int
     */
    public static int waysdp(int a, int b, int s) {
        // 动态规划表
        // (i, j, step),i的变化范围是[0...9], j的变化范围是[0...8], step的变化范围是[0...s]
        int[][][] dp = new int[10][9][s + 1];
        // 第0层的面
        dp[a][b][0] = 1;//(a, b)位置为1，其他位置为0，数组初始化时就为0，不用再给其他位置赋值。
        // 由第0层推算其他层
        for (int step = 1; step <= s; step++) {// 按层来枚举
            // 计算出每层中(i, j)位置的值
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 9; j++) {
                    dp[i][j][step] = getValue(dp, i - 1, j + 2, step - 1) +
                            getValue(dp, i - 2, j + 1, step - 1) +
                            getValue(dp, i - 2, j - 1, step - 1) +
                            getValue(dp, i - 1, j - 2, step - 1) +
                            getValue(dp, i + 1, j - 2, step - 1) +
                            getValue(dp, i + 2, j - 1, step - 1) +
                            getValue(dp, i + 2, j + 1, step - 1) +
                            getValue(dp, i + 1, j + 2, step - 1);
                }
            }

        }

        return dp[0][0][s];
    }

    /**
     * 在dp表中，得到dp[i][j][step]的值，但是如果(i, j)位置越界的话，返回0
     *
     * @param dp   dp表
     * @param i    马现在所在位置的“纵坐标”，纵坐标i的范围是0~9
     * @param j    马现在所在位置的“横坐标”，也就是横坐标j的范围是0~8
     * @param step 当前跳的是第step步
     * @return int
     */
    public static int getValue(int[][][] dp, int i, int j, int step) {
        // 越界就返回0
        if (i < 0 || i > 9 || j < 0 || j > 8) {
            return 0;
        }
        // 不越界
        return dp[i][j][step];
    }

    public static void main(String[] args) {
        int x = 7;
        int y = 7;
        int step = 10;
        System.out.println(ways(x, y, step));
        System.out.println(waysdp(x, y, step));
    }
}
